package bloomfilter;

import java.util.BitSet;

class SimpleHash {

    public int cap;//容量
    public int rand;//随机种子

    public SimpleHash(int cap, int rand) {
        this.cap = cap;
        this.rand = rand;
    }

    /**
     * 哈希函数
     *
     * @param s 根据字符串返回一个哈希值
     * @return
     */
    int hash(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            res = res * rand + s.charAt(i);
        }
        return res & (cap - 1);
    }
}


public class BloomFilter {
    public static void main(String[] args) {
        BloomFilter b = new BloomFilter();
        b.add("www");
        b.add("aaa");
        b.add("acb");
        b.add("abc");

        System.out.println(b.contains("abc"));
    }
    private static int DEFAULT_SIZE;
    BitSet bitSet;
    public int usedSize;//存储的个数
    public int[] rad = {1, 3, 7, 13, 26, 74};//随机种子
    SimpleHash[] simpleHashes;

    public BloomFilter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        simpleHashes = new SimpleHash[rad.length];
        //根据每个随机种子生成对应的哈希函数
        for (int i = 0; i < rad.length; i++) {
            simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, rad[i]);
        }
    }

    public void add(String s) {
        for (int i = 0; i < simpleHashes.length; i++) {
            bitSet.set(simpleHashes[i].hash(s));
        }
        usedSize++;
    }

    public boolean contains(String s) {
        for (int i = 0; i < simpleHashes.length; i++) {
            if (!bitSet.get(simpleHashes[i].hash(s))) {
                return false;
            }
        }
        return true;
    }
}
